// 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

// 提醒一下，二叉搜索树满足下列约束条件：

// 节点的左子树仅包含键 小于 节点键的节点。
// 节点的右子树仅包含键 大于 节点键的节点。
// 左右子树也必须是二叉搜索树。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 逻辑错误

// 输入
// [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
// 输出
// [25,31,21,31,5,26,15,null,null,null,3,null,null,null,8]
// 预期结果
// [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

class Solution {
public:
    unordered_map<TreeNode*,int> hash;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root,0,0);
        return root;
    }
    int dfs(TreeNode* root,int rootVal,int pos){
        if(root == NULL){
            return 0;
        }
        int val;
        if(hash.count(root)){
            return hash[root];
        }
        else{
            if(pos==0){
                rootVal=0;
            }
            else{
                rootVal = rootVal;
            }
        }
        val = rootVal + root->val + dfs(root->right,rootVal,0);
        hash[root] = val;
        root->val = val;
        dfs(root->left,hash[root],1);
        return val;
    }
};